/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

import org.junit.Test;

/**
 * <p>
 * 找出第一个不在数组中出现的元素 Given [1,2,0] return 3, 
 * [3,4,-1,1] return 2.
 * 时间o(n)
 * 空间O(1)
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月21日
 */
public class FirstMissingPositive {

    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i=0;i<n;i++){
            if(nums[i]>0 && nums[i]<=n){
                if(nums[i]>0 && nums[i]<=n){
                    if(nums[i]-1!=i && nums[nums[i]-1] !=nums[i]){
                        //交换相应的值
                        int tmp = nums[nums[i]-1];
                        nums[nums[i]-1] = nums[i];
                        nums[i] = tmp;
                        //交换后，还需要对新的arr[i]进行判断
                        i--;
                    }
                }
            }
        }
        for(int i=0;i<n;i++){
            //输出第一个不匹配的数字
            if(nums[i]-1 !=i){
                return i+1;
            }
            //如果没有找到，输出长度+1的数字
        }
        return n+1;
    }
    @Test
    public void testCase(){
        int []nums  = {5,3,-1,1};
        System.out.println(firstMissingPositive(nums));
    }
}
